#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <errno.h>
#include "kernel_list.h"

#define UPDATE_INTERVAL 1
#define ROUTE_UPDATE_INTERVAL 30

struct node_me
{
	unsigned short port;
	char *name;
	struct list_head nei_list;
	struct list_head next_node;
};
struct node_nei
{
	unsigned short port;
	char *name;
	double cost;
	struct list_head list;
	struct node_me *parent;
};

static int dijkstra_start;

int main(int argc, char **argv)
{
	struct node_me *me = NULL;
	struct sockaddr_in my_addr;
	struct sockaddr from;
	socklen_t fromlen = sizeof from;
	int sockfd, ret;
	char buffer[4096];
	struct timeval tv;

	if (argc != 4) {
		printf("parameter error!\n");
	}
	me = malloc(sizeof(struct node_me));
	if (!me) {
		goto end;
	}
	INIT_LIST_HEAD(&(me->nei_list));
	INIT_LIST_HEAD(&(me->next_node));
	me->name = strdup(argv[1]);
	sscanf(argv[2], "%hu", &(me->port));
	if (config(argv[3], me) < 0) {
		goto end;
	}

	signal(SIGPIPE, SIG_IGN);
	signal(SIGALRM, on_alarm);
	set_ticker(ROUTE_UPDATE_INTERVAL * 1000);

	sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	if (sockfd < 0)
		goto end;
	bzero(&my_addr, sizeof my_addr);
	my_addr.sin_family = AF_INET;
	my_addr.sin_port = htons(me->port);
	my_addr.sin_addr.s_addr = INADDR_ANY;
	if (bind(sockfd, (struct sockaddr *)&my_addr, sizeof my_addr) < 0) {
		perror("bind");
		goto end;
	}
	tv.tv_sec = UPDATE_INTERVAL;
	tv.tv_usec = 0;
	if (setsockopt(sockfd, SOL_SOCKET, SO_RCVTIMEO, &tv, sizeof tv) < 0) {
		perror("setsockopt");
		goto end;
	}
	
	while (1) {
		if (dijkstra_start)
			dijkstra(me);
		memset(buffer, 0, sizeof buffer);
		ret = recvfrom(sockfd, buffer, sizeof buffer, 0, &from, &fromlen);
		if (ret < 0) {
			if (errno == EWOULDBLOCK) {
				broadcast(sockfd, me);
				continue;
			}
			else if (errno == EINTR) {
				continue;
			}
			else {
				perror("recvfrom");
				goto end;
			}
		}
		add_node(buffer, me);
		broadcast(sockfd, me);
	}
	
end:
	return 0;
}

static int compare(const void *a, const void *b)
{
	const struct node_nei *p1 = (const struct node_nei *)a;
	const struct node_nei *p2 = (const struct node_nei *)b;

	return ((p2->cost - p1->cost) > 0) ? 1: 0;
}

static void dijkstra(struct node_me *me)
{
	struct s_gather
	{
		struct node_me *node;
		struct list_head list;
	};
	struct ret_gather
	{
		struct node_nei *node;
		struct ret_gather *left;
		struct ret_gather *sibling;
	};
	struct s_gather *s = NULL, *s2;
	struct ret_gather *root = NULL;
	LIST_HEAD(s_head);
	int n = 1, s_n = 1;
	struct list_head *ptr = NULL, *ptr2 = NULL, *ptr3;
	PQ *desc = NULL;
	PQ_element *e = NULL;
	struct node_nei *nei = NULL;
	struct node_me *node;

	list_for_each(ptr, &(me->next_node)) {
		n++;
	}
	s = malloc(sizeof(struct s_gather));
	s->node = me;
	list_add_tail(&(s->list), &s_head);
	printf("least-cost path to node ");
	desc = create_PQ(10, compare, NULL);
	root = malloc(sizeof(struct ret_gather));
	root->node = malloc(sizeof(struct node_nei));
	root->node->port = me->port;
	root->node->name = me->name;
	root->node->cost = 0;
	root->left = NULL;
	root->sibling = NULL;

	while (s_n < n) {
		list_for_each(ptr, &s_head) {
			s = list_entry(ptr, struct s_gather, list);
			if (strcmp(s->node->name, me->name))
				printf("%s: ", s->node->name);
			list_for_each(ptr3, &(s->node->nei_list)) {
				nei = list_entry(ptr3, struct node_nei, list);
				list_for_each(ptr2, &s_head) {
					s2 = list_entry(ptr2, struct s_gather, list);
					if (!strcmp(s2->node->name, nei->name))
						break;
				}
				if (ptr2 == &s_head) {
					e = malloc_PQ(sizeof(struct node_nei));
					struct node_nei *data = ELEMENT_DATA(e);
					data->name = nei->name;
					data->port = nei->port;
					data->cost = nei_cost;
					inset_PQ(desc, e);
				}
			}
		}
		e = extract_PQ(desc);
		nei = ELEMENT_DATA(e);
		list_for_each(ptr, &(me->next_node)) {
			node = list_entry(ptr, struct node_me, next_list);
			if (!strcmp(node->name, nei->name)) {
				s2 = malloc(sizeof(struct s_gather));
				s2->node = node;
				list_add_tail(s2, &s_head);
				free_PQ(e);
				s_n++;
				break;
			}
		}
		add_to_tree(root, );
	}
}

static void add_node(const char *buf, struct node_me *me)
{
	struct node_me *next = NULL;
	struct node_nei *nei = NULL;
	char *cp_buf = NULL;
	char *front = NULL, *back = NULL, *tmp = NULL;
	int n;

	if (!buf)
		goto end;
	cp_buf = strdup(buf);
	n = strlen(buf);
	front = cp_buf;
	next = malloc(sizeof(struct node_me));
	INIT_LIST_HEAD(&(next->nei_list));
	list_add_tail(&(next->next_node), &(me->next_node));
	back = strchr(buf, '\n');
	*back = '\0';
	back++;
	tmp = strchr(buf, ' ');
	*tmp = '\0';
	tmp++;
	next->name = strdup(front);
	front = tmp;
	sscanf(front, "%hu", &(next->port));
	while (back < cp_buf + n) {
		nei = malloc(sizeof(struct node_nei));
		list_add_tail(&(nei->list), &(next->nei_list));
		front = back;
		back = strchr(back, '\n');
		*back = '\0';
		back++;
		tmp = strchr(front, ' ');
		*tmp = '\0';
		tmp++;
		nei->name = strdup(front);
		front = tmp;
		tmp = strchr(front, ' ');
		*tmp = '\0';
		tmp++;
		sscanf(front, "%lf", &(nei->cost));
		front = tmp;
		sscanf(front, "%hu", &(nei->port));
		nei->parent = next;
	}
	free(cp_buf);
end:
	return;	
}

static void broadcast(int sockfd, const struct node_me *me)
{
	struct sockaddr_in cli;
	struct node_nei *p = NULL;
	struct node_me *next;
	struct list_head *ptr = NULL, *ptr2 = NULL;
	char buffer[4096], *pointer = buffer;
	int n;

	sprintf(pointer, "%s %hu\n", me->name, me->port);
	pointer += strlen(pointer);
	list_for_each(ptr, &(me->nei_list)) {
		p = list_entry(ptr, struct node_nei, list);
		sprintf(pointer, "%s %lf %hu\n", p->name, p->cost, p->port);
		pointer += strlen(pointer);
	}
	n = strlen(buffer);

	list_for_each(ptr, &(me->nei_list)) {
		p = list_entry(ptr, struct node_nei, list);
		bzero(&cli, sizeof cli);
		cli.sin_family = AF_INET;
		cli.sin_port = htons(p->port);
		inet_pton(AF_INET, "127.0.0.1", &cli.sin_addr.s_addr);
		sendto(sockfd, buffer, n, 0, (struct sockaddr *)&cli, sizeof cli);
	}

	list_for_each(ptr2, &(me->next_node)) {
		pointer = buffer;
		next = list_entry(ptr2, struct node_me, next_list);
		sprintf(pointer, "%s %hu\n", next->name, next->port);
		pointer += strlen(pointer);
		list_for_each(ptr, &(next->nei_list)) {
			p = list_entry(ptr, struct node_nei, list);
			sprintf(pointer, "%s %lf %hu\n", p->name, p->cost, p->port);
			pointer += strlen(pointer);
		}
		n = strlen(buffer);

		list_for_each(ptr, &(next->nei_list)) {
			p = list_entry(ptr, struct node_nei, list);
			if (!strcmp(p->name, next->name))
				continue;
			bzero(&cli, sizeof cli);
			cli.sin_family = AF_INET;
			cli.sin_port = htons(p->port);
			inet_pton(AF_INET, "127.0.0.1", &cli.sin_addr.s_addr);
			sendto(sockfd, buffer, n, 0, (struct sockaddr *)&cli, sizeof cli);
		}
	}
}

static int config(const char *config_file, struct node_me *me)
{
	FILE *fp = NULL;
	int ret = -1;
	int n;
	char buffer[4096];
	struct node_nei *nei = NULL;
	char *saveptr = NULL, *tmp = NULL;

	if (!config_file)
		goto end;
	fp = fopen(config_file, "r");
	if (!fp) {
		perror("fopen");
		goto end;
	}
	fgets(buffer, sizeof buffer, fp);
	sscanf(buffer, "%d", &n);
	memset(buffer, 0, sizeof buffer);
	while (fgets(buffer, sizeof buffer, fp)) {
		nei = malloc(sizeof(struct node_nei));
		tmp = strtok_r(buffer, "\t \r\n", &saveptr);
		nei->name = strdup(tmp);
		tmp = strtok_r(buffer, "\t \r\n", &saveptr);
		sscanf(tmp, "%lf", &(nei->cost));
		tmp = strtok_r(buffer, "\t \r\n", &saveptr);
		sscanf(tmp, "%hu", &(nei->port));
		list_add_tail(&(nei->list), &(me->nei_list));
		memset(buffer, 0, sizeof buffer);
	}
	fclose(fp);
	ret = 0;
end:
	return ret;
}

static void on_alarm(int signo)
{
	dijkstra_start = 1;
	return;
}

static int set_ticker(int n_msecs)
{
	struct itimerval timer;
	long n_sec, n_usecs;

	n_sec = n_msecs / 1000;
	n_usecs = (n_msecs % 1000) * 1000L;

	timer.it_interval.tv_sec = n_sec;
	timer.it_interval.tv_usec = n_usecs;
	timer.it_value.tv_sec = n_sec;
	timer.it_value.tv_usec = n_usecs;
	return setitimer(ITIMER_REAL, &timer, NULL);
}
